partiels/091105/partiel_Mathsdis_S1_Novembre 09.tex.bak

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  10 \usepackage[dvips]{graphics}
  11 \usepackage{epsfig}
  12 \usepackage{calc}
  13 \usepackage{tabls}
  14 \usepackage{slashbox}
  15 \usepackage{times}
  16 \usepackage{tabularx}
  17 \usepackage{textcomp}
  18 \usepackage{pst-all}
  19 \usepackage[a4paper]{geometry}
  20
  21 \input{symboles.sty}
  22 \geometry{hmargin=1cm, vmargin=1.5cm}
  23
  24 \title{
  25 Département d'informatique \\
  26 Partiel de mathématiques discrètes\\
  27 Semestre 1 (Novembre 09)\\
  28 }
  29
  30 \date{}
  31
  32 \begin{document}
  33 \maketitle
  34
  35 \noindent Seule une fiche manuscrite de format A5 est autorisée.
  36
  37 \noindent\begin{tabular}{ll}
  38 Nom: &.............................. \\
  39 Prénom: &..............................
  40 \end{tabular}
  41
  42 \section{QCM}
  43
  44 Cette partie contient 60 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\
  45
  46 Q. 1. $\pi$ est rationnel.
  47 L'assertion proposée est vraie ou fausse ?\\
  48
  49 Q. 2. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $a \in A$. L'assertion proposée est vraie ou fausse ?\\
  50
  51 Q. 3. L'intersection entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles.
  52 L'assertion proposée est vraie ou fausse ?\\
  53
  54 Q. 4. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{d,e,f\} \in A$. L'assertion proposée est vraie ou fausse ?\\
  55
  56 Q. 5. L'intersection de deux ensembles est l'ensemble des éléments appartenant à au moins un des deux ensembles.
  57 L'assertion proposée est vraie ou fausse ?\\
  58
  59 Q. 6. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs.L'assertion proposée est vraie ou fausse ?\\
  60
  61 Q. 7.
  62 Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$.
  63 Si $t_1 . t_2 = 0$ alors $t_1 = \overline{t_2}$.
  64  L'assertion proposée est vraie ou fausse ?
  65 \\
  66
  67 Q. 8.
  68 Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$.
  69 Si $t_1 . t_2 = 0$ alors $t_1$ ou $t_2$ sont nuls.
  70  L'assertion proposée est vraie ou fausse ?
  71 \\
  72
  73 Q. 9. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 8 éléments.
  74 L'assertion proposée est vraie ou fausse ?\\
  75
  76 Q. 10. Le complémentaire de $A$ dans $E$ est l'ensembles des éléments de $E$ qui ne sont pas dans $A$.
  77 L'assertion proposée est vraie ou fausse ?\\
  78
  79 Q. 11. Par convention, $\varnothing$ a 0 élément.
  80 L'assertion proposée est vraie ou fausse ?\\
  81
  82 Q. 12. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{d,e,f\} \in A$.
  83 L'assertion proposée est vraie ou fausse ?\\
  84
  85 Q. 13. Le cardinal d'un ensemble fini est son nombre d'éléments.
  86 L'assertion proposée est vraie ou fausse ?\\
  87
  88 Q. 14. Il existe un unique ensemble vide.L'assertion proposée est vraie ou fausse ?\\
  89
  90 Q. 15.
  91 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
  92 le . est le symbole du ET logique.
  93 L'égalité $\overline{a}.b.\overline{c}.\overline{d} = 1$ si et seulement si $a+\overline{b} + c+ d =0$. L'assertion proposée est vraie ou fausse ?\\
  94
  95 Q. 16. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments.
  96 L'assertion proposée est vraie ou fausse ?\\
  97
  98 Q. 17. Le complémentaire de $A$ dans $E$ est l'ensembles des éléments de $E$ qui ne sont pas dans $A$.L'assertion proposée est vraie ou fausse ?\\
  99
 100 Q. 18. Le complémentaire des entiers pairs dans $\N$ est égal à l'ensemble des entiers impairs.L'assertion proposée est vraie ou fausse ?\\
 101
 102 Q. 19. $\pi$ est irrationnel.
 103 L'assertion proposée est vraie ou fausse ?\\
 104
 105 Q. 20. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $ \{c \} \subset A$.
 106 L'assertion proposée est vraie ou fausse ?\\
 107
 108 Q. 21.
 109 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 110 le . est le symbole du ET logique.
 111 L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $a.b$ vaut 0. L'assertion proposée est vraie ou fausse ?\\
 112
 113 Q. 22. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 4 éléments.L'assertion proposée est vraie ou fausse ?\\
 114
 115 Q. 23. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$.L'assertion proposée est vraie ou fausse ?\\
 116
 117 Q. 24. $\N$ est un ensemble infini.L'assertion proposée est vraie ou fausse ?\\
 118
 119 Q. 25. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \subset A$.L'assertion proposée est vraie ou fausse ?\\
 120
 121 Q. 26. $\sin(1)$ est irrationnel.L'assertion proposée est vraie ou fausse ?\\
 122
 123 Q. 27. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \in A$.
 124 L'assertion proposée est vraie ou fausse ?\\
 125
 126 Q. 28. $\Z$ est un ensemble infini.
 127 L'assertion proposée est vraie ou fausse ?\\
 128
 129 Q. 29.
 130 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 131 le . est le symbole du ET logique.
 132 L'expression $a+ \overline{b} + \overline{a}.b + \overline{c}$ est équivalent à $\overline{c} + 1$. L'assertion proposée est vraie ou fausse ?\\
 133
 134 Q. 30. $\Z$ est un ensemble infini.L'assertion proposée est vraie ou fausse ?\\
 135
 136 Q. 31. $A \cup B$ est la réunion de $A$ et de $B$.
 137 L'assertion proposée est vraie ou fausse ?\\
 138
 139 Q. 32.
 140 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 141 le . est le symbole du ET logique.
 142 L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion  proposée est vraie ou fausse ?\\
 143
 144 Q. 33. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$.
 145 L'assertion proposée est vraie ou fausse ?\\
 146
 147 Q. 34. $A \cap B$ est la réunion de $A$ et de $B$.L'assertion proposée est vraie ou fausse ?\\
 148
 149 Q. 35. $e$ est irrationnel.
 150 L'assertion proposée est vraie ou fausse ?\\
 151
 152 Q. 36.
 153 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 154 le . est le symbole du ET logique.
 155 L'expression  $\overline{a}.b + a.\overline{b}$ est vraie quand $a$ et $b$ sont différents. L'assertion proposée est vraie ou fausse ?\\
 156
 157 Q. 37. La réunion entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles.
 158 L'assertion proposée est vraie ou fausse ?\\
 159
 160 Q. 38. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \in A$.L'assertion proposée est vraie ou fausse ?\\
 161
 162 Q. 39.
 163 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 164 le . est le symbole du ET logique.
 165 L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ?\\
 166
 167 Q. 40. $A \cap B$ est la réunion de $A$ et de $B$.
 168 L'assertion proposée est vraie ou fausse ?\\
 169
 170 Q. 41. L'intersection de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$.
 171 L'assertion proposée est vraie ou fausse ?\\
 172
 173 Q. 42. $\pi$ est irrationnel.L'assertion proposée est vraie ou fausse ?\\
 174
 175 Q. 43. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments.L'assertion proposée est vraie ou fausse ?\\
 176
 177 Q. 44.
 178 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression
 179 $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1
 180  L'assertion proposée est vraie ou fausse ?
 181 \\
 182
 183 Q. 45.
 184 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression
 185 $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 1
 186  L'assertion proposée est vraie ou fausse ?
 187 \\
 188
 189 Q. 46. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{\{a,b\}\} \subset A$.
 190 L'assertion proposée est vraie ou fausse ?\\
 191
 192 Q. 47. $\sin(1)$ est rationnel.L'assertion proposée est vraie ou fausse ?\\
 193
 194 Q. 48. $A \cup B$ est l'intersection de $A$ et de $B$.
 195 L'assertion proposée est vraie ou fausse ?\\
 196
 197 Q. 49. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 64 éléments.
 198 L'assertion proposée est vraie ou fausse ?\\
 199
 200 Q. 50. $A \cap B$ est l'intersection de $A$ et $B$.
 201 L'assertion proposée est vraie ou fausse ?\\
 202
 203 Q. 51. $\sin(1)$ est rationnel.
 204 L'assertion proposée est vraie ou fausse ?\\
 205
 206 Q. 52. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs.
 207 L'assertion proposée est vraie ou fausse ?\\
 208
 209 Q. 53.
 210 Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression
 211 $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 0
 212  L'assertion proposée est vraie ou fausse ?
 213 \\
 214
 215 Q. 54. $A \cup B$ est la réunion de $A$ et de $B$.L'assertion proposée est vraie ou fausse ?\\
 216
 217 Q. 55.
 218 On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et
 219 le . est le symbole du ET logique.
 220 L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion  proposée est vraie ou fausse ?\\
 221
 222 Q. 56. $A \cap B$ est l'intersection de $A$ et $B$.L'assertion proposée est vraie ou fausse ?\\
 223
 224 Q. 57. Le complémentaire des entiers pairs dans $\N$ est égal à l'ensemble des entiers impairs.
 225 L'assertion proposée est vraie ou fausse ?\\
 226
 227 Q. 58. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ et à $B$.
 228 L'assertion proposée est vraie ou fausse ?\\
 229
 230 Q. 59. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $a \in A$.
 231 L'assertion proposée est vraie ou fausse ?\\
 232
 233 Q. 60. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$.
 234 L'assertion proposée est vraie ou fausse ?\\
 235
 236
 237
 238 \begin{center}
 239 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 240 \hline
 241 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 242 \hline
 243 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 244 \hline
 245 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 246 \hline
 247 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 248 \hline
 249 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 250 \hline
 251 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 252 \hline
 253 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 254 \hline
 255 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 256 \hline
 257 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 258 \hline
 259 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 260 \hline
 261 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 262 \hline
 263 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
 264 \hline
 265 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
 266 \hline
 267 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
 268 \hline
 269 Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\
 270 \hline
 271 Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\
 272 \hline
 273 Q. 46 & &  & Q. 47 & &  & Q. 48 & &  \\
 274 \hline
 275 Q. 49 & &  & Q. 50 & &  & Q. 51 & &  \\
 276 \hline
 277 Q. 52 & &  & Q. 53 & &  & Q. 54 & &  \\
 278 \hline
 279 Q. 55 & &  & Q. 56 & &  & Q. 57 & &  \\
 280 \hline
 281 Q. 58 & &  & Q. 59 & &  & Q. 60 & &  \\
 282 \hline
 283 \end{tabular}
 284 \end{center}
 285 %\end{huge}
 286
 287
 288
 289
 290
 291
 292
 293 \section{Problèmes}
 294
 295
 296
 297
 298
 299
 300 \subsection{Théorie des ensembles}
 301 Rappel: pour deux ensembles $A$ et $B$, on appelle \emph{différence symétrique}, noté $A\Delta B$, l'ensemble défini par
 302 \[
 303 A \Delta B = (A \cup B) \setminus (A \cap B)
 304 \]
 305 c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux.
 306
 307
 308 Soit $A$, $B$ et $C$ trois ensembles.
 309
 310 \begin{enumerate}
 311 \item Montrer que l'opérateur est commutatif.
 312 \item Montrer que l'opérateur possède un élément neutre que l'on explicitera.
 313 \item Montrer que si $A \Delta B = A \Delta C$ alors $B = C$.
 314 \end{enumerate}
 315
 316 \subsection{Algèbre de Boole 1}
 317
 318 A l'aide des  méthodes de votre choix (Karnaugh ou consensus),
 319 réécrire les expression suivantes
 320 en une somme qui contient le moins de monomes possibles.
 321 \begin{enumerate}
 322 \item $A =\overline{c}\overline{d}b + cab + \overline{c}dab + c\overline{d}\overline{a}b + ca\overline{b}$. % ac + ab + b\overline{d}
 323
 324 \item $B =
 325   \overline{a}b\overline{c}\overline{d}+
 326   ab\overline{c} +
 327   a\overline{b}\overline{c}d +
 328   acd +
 329   abc\overline{d} +
 330   \overline{a}\overline{b}d$
 331 % \overline{a}b\overline{c}\overline{d} + ab + \overline{b}d
 332 \end{enumerate}
 333
 334
 335 \subsection{Algèbre de Boole 2}
 336 On considère le jeu avec une équipe de quatre candidats dont un chef d'équipe.
 337 Chaque candidat dispose d'un
 338 boitier lui permettant de donner un vote de type oui/non.
 339 Un affichage central présente l'avis de la majorité des candidats.
 340 Lorsqu'il y a le même nombre de votes \og oui\fg{} que de vôtes \og non\fg{}
 341 le vote du chef d'equipe est
 342 prépondérant.
 343 \begin{enumerate}
 344 \item Construire la table de vérité  du système central d'affichage;
 345 \item Exprimez l'affichage centrale en FCD;
 346 \item Formez une expression booléenne minimale de l'affichage.
 347 \end{enumerate}
 348 \end{document}